from typing import List


class Solution:
    def mergeSort(self, nums: List) -> List:
        if len(nums) < 2:
            return nums
        middle = len(nums) // 2
        left = nums[:middle]
        right = nums[middle:]

        return self.merge(self.mergeSort(left), self.mergeSort(right))

    def merge(self, nums1: List, nums2: List) -> List:
        result = []
        while len(nums1) > 0 and len(nums2) > 0:
            if nums1[0] <= nums2[0]:
                result.append(nums1.pop(0))
            else:
                result.append(nums2.pop(0))
        while len(nums1) > 0:
            result.append(nums1.pop(0))
        while len(nums2) > 0:
            result.append(nums2.pop(0))
        return result


if __name__ == '__main__':
    t = [3, 1, 5, -6, 7, 12, 2, 9, 10]
    x = Solution()
    print(x.mergeSort(t))
